HJ86 求最大连续bit数

本节目标：理解“HJ86 求最大连续bit数”的核心思路，并能把它用于实际开发或面试表达。 描述 求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1 数据范围：数据组数：1≤t≤5, 1≤n≤500000 进阶：时间复杂度： O(logn) ，空间复杂度： O(1) 输入描述： 输入一个int类型数字 输出描述： 输出转成二进制之后连续1的个数 示例1 输入： 200 ==复制== 输出： 2 ==复制== 说明： 200的二进制表示是11001000，最多有2个连续的1。

为了找到一个整数的二进制表示中1的最大连续数，我们可以通过不断地将这个数与自己减1后的结果进行按位与操作（&），并计数进行了多少次操作，直到这个数变为0。这种方法的核心在于，每次n & (n-1)操作实际上都会去除n二进制表示中最右边的1，因此，通过这种方式可以有效地计算出1的连续长度。

不过，这个方法直接计算的是1的总个数，并不能直接用来计算最大连续1的个数。为了计算最大连续1的个数，我们可以遍历这个数的二进制表示，统计连续1的最大长度。

下面是Python代码示例：

def max_consecutive_ones(n):

将整数转换为二进制字符串

binary_str = bin(n)[2:] # bin函数返回的字符串包含前缀'0b'，所以使用切片[2:]去除 max_count = 0 # 连续1的最大数量 count = 0 # 当前连续1的数量 for char in binary_str: if char == '1': count += 1 # 如果字符是'1'，增加当前计数 max_count = max(max_count, count) # 更新最大连续1的数量 else: count = 0 # 如果字符不是'1'，重置当前计数 return max_count

输入

n = int(input())

输出

print(max_consecutive_ones(n))

这段代码首先使用bin函数将整数n转换为二进制字符串表示，然后遍历这个字符串，使用一个计数器count来统计当前的连续1的个数，同时用另一个变量max_count来记录遇到的最大连续1的个数。每次遇到'1'字符时，count自增；遇到'0'字符时，将count重置为0。最终，max_count即为所求的最大连续1的个数。